# 导入 np
import numpy as np


def if_value(vallue):
    return str(int(vallue)) if vallue != 0 else ' '


def ivn(vallue, i_):
    i = i_ - 1
    num_non_zero, value = arr_nonzero_to_value(vallue)
    if num_non_zero == 1:
        pass
        if i == 1:

            return f"* {value[0]} *"
        else:
            return f"* * *"
    else:
        return f"{if_value(vallue[i * 3 + 0])} {if_value(vallue[i * 3 + 1])} {if_value(vallue[i * 3 + 2])}"


def ivn_ok(vallue):
    num_non_zero, value = arr_nonzero_to_value(vallue)
    return int(value[0])


# 打印矩阵
def printArr(arr):
    if detection(arr):
        printArr_ok(arr)
    else:
        printArr_on(arr)


def printArr_ok(arr):
    print("=============================")
    for i in range(9):
        arr_v = arr[i]
        l0 = f"|| {ivn_ok(arr_v[0])} {ivn_ok(arr_v[1])} {ivn_ok(arr_v[2])} || {ivn_ok(arr_v[3])} {ivn_ok(arr_v[4])} {ivn_ok(arr_v[5])} || {ivn_ok(arr_v[6])} {ivn_ok(arr_v[7])} {ivn_ok(arr_v[8])} || "
        print(l0)
        if (i + 1) % 3 == 0:
            print("=============================")
    pass


def printArr_on(arr):
    print(
        "=============================================================================")
    for i in range(9):
        arr_v = arr[i]
        l0 = f"|| {ivn(arr_v[0], 1) } | {ivn(arr_v[1], 1) } | {ivn(arr_v[2], 1)} || {ivn(arr_v[3], 1) } | {ivn(arr_v[4], 1) } | {ivn(arr_v[5], 1)} || {ivn(arr_v[6], 1) } | {ivn(arr_v[7], 1) } | {ivn(arr_v[8], 1)} || "
        l1 = f"|| {ivn(arr_v[0], 2) } | {ivn(arr_v[1], 2) } | {ivn(arr_v[2], 2)} || {ivn(arr_v[3], 2) } | {ivn(arr_v[4], 2) } | {ivn(arr_v[5], 2)} || {ivn(arr_v[6], 2) } | {ivn(arr_v[7], 2) } | {ivn(arr_v[8], 2)} || "
        l2 = f"|| {ivn(arr_v[0], 3) } | {ivn(arr_v[1], 3) } | {ivn(arr_v[2], 3)} || {ivn(arr_v[3], 3) } | {ivn(arr_v[4], 3) } | {ivn(arr_v[5], 3)} || {ivn(arr_v[6], 3) } | {ivn(arr_v[7], 3) } | {ivn(arr_v[8], 3)} || "
        print(l0)
        print(l1)
        print(l2)

        if (i + 1) % 3 == 0:
            print(
                "=============================================================================")
        else:
            print("-----------------------------------------------------------------------------")
    pass


def init():
    # 使用np 创建一个 3*3*9 的矩阵
    arr = np.zeros((9, 9, 9))
    # 打印矩阵
    # printArr(arr)
    print(f"********************************************")
    # 设置矩阵的数值 从1 到9
    for i in range(9):
        for j in range(9):
            for k in range(9):
                arr[i][j][k] = k + 1
    # printArr(arr)

    return arr


# 当前节点 除了 v 其余数据都设成0  或者只把v 设成0
def mark_v(arr_v, v, b=True):
    # 除去v 以外的值 都写成0
    for i in range(9):
        if b:
            if i != v:
                arr_v[i] = 0
        else:
            if i == v:
                arr_v[i] = 0
    return arr_v


# 标记
def mark(arr, x_, y_, v_):
    x = x_ - 1
    y = y_ - 1
    v = v_ - 1  # -1 把数 值变成索引
    # 矩阵中 x,y 位置值
    arr_v = arr[x][y]
    arr[x][y] = mark_v(arr_v, v)
    # # 修改矩阵中 x位置的值 所有y的值 当前行 所有列 都去除v
    for i in range(9):
        if i != y:
            arr[x][i] = mark_v(arr[x][i], v, False)
    # # 修改矩阵中 y位置的值 所有x的值 当前列 所有行都除去v
    for i in range(9):
        if i != x:
            arr[i][y] = mark_v(arr[i][y], v, False)

    x_0 = x // 3
    x_1 = x_0 + 1

    y_0 = y // 3
    y_1 = y_0 + 1

    for i in range(x_0 * 3, x_1 * 3):
        for j in range(y_0 * 3, y_1 * 3):
            if i != x and j != y:
                # 当前3*3 所以都去除 v
                arr[i][j] = mark_v(arr[i][j], v, False)
    return arr


def arr_nonzero_to_value(arr):
    # 获取非0 索引
    non_zero_indices = np.nonzero(arr)[0]
    # 统计
    num_non_zero = len(non_zero_indices)
    # 索引对应的数据
    value = non_zero_indices + 1

    return num_non_zero, value


# 检测错误
def detection_error(arr):
    for i in range(9):
        for j in range(9):
            num_non_zero, value = arr_nonzero_to_value(arr[i][j])
            if num_non_zero == 0:
                return False
    return True


# 检测时候完成
def detection(arr):
    for i in range(9):
        for j in range(9):
            num_non_zero, value = arr_nonzero_to_value(arr[i][j])
            if num_non_zero > 1:
                return False
    return True


def AutomaticSimpleProcessing(arr, value_list):
    b = True
    while b:
        b = False
        # 根据 已填充的值， 计算
        for i in range(9):
            for j in range(9):
                # 非零数据个数 和 非零的数
                num_non_zero, value = arr_nonzero_to_value(arr[i][j])
                # 格子唯一的时候
                if num_non_zero == 1:
                    index = i * 100 + j * 10 + value[0] + 111
                    if index not in value_list:
                        value_list.append(index)
                        b = True
                        arr = mark(arr, i + 1, j + 1, value[0])
                else:
                    # 存在多个数据
                    # 获取当前行列value
                    # 行摒除、列摒除、九宫格摒除
                    for non_zero_value in value:
                        # 当前行列中 该元素唯一
                        set_i = set()  # 记录行唯一
                        set_j = set()  # 记录列唯一
                        set_ij = set()  # 记录3*3 唯一

                        for ij in range(9):
                            if ij != j:
                                _, value_i = arr_nonzero_to_value(arr[i][ij])
                                set_i.update(value_i)
                            if ij != i:
                                _, value_j = arr_nonzero_to_value(arr[ij][j])
                                set_j.update(value_j)

                        # 计算 3*3 坐标
                        x_0 = i // 3
                        x_1 = x_0 + 1
                        y_0 = j // 3
                        y_1 = y_0 + 1
                        # opi = 0
                        for i_ in range(x_0 * 3, x_1 * 3):
                            for j_ in range(y_0 * 3, y_1 * 3):
                                if i != i_ or j != j_:
                                    # opi = opi+1
                                    # 当前3*3 所以都去除 v
                                    _, value_ij = arr_nonzero_to_value(arr[i_][j_])
                                    set_ij.update(value_ij)
                        # print(f"{opi = }")
                        # 当当前元素不在列表中的时候 说明 元素唯一
                        if non_zero_value not in set_i or non_zero_value not in set_j or non_zero_value not in set_ij:
                            index = i * 100 + j * 10 + non_zero_value + 110
                            if index not in value_list:
                                value_list.append(index)
                                b = True
                                print(f"**  x = {i + 1}  y = {j + 1}  v= {non_zero_value}")
                                arr = mark(arr, i + 1, j + 1, non_zero_value)
                                # continue
                            else:
                                print(
                                    f"打印说明出错了，当前坐标存在， 理论上 不会重复 {non_zero_value = } {set_i = } {set_j = } {set_ij = } {index = }")
                    pass

    return arr


# 假设 填充
def assume(arr, value_list):
    arr_copy = np.copy(arr)
    value_list_copy = value_list.copy()
    for i in range(9):
        for j in range(9):
            num_non_zero, value = arr_nonzero_to_value(arr[i][j])
            # 格子唯一的时候
            if num_non_zero != 1:
                # 尝试某一格子 所有可能
                for v in value:
                    arr_copy_ij = np.copy(arr_copy)
                    value_list_copy_ij = value_list_copy.copy()
                    arr_copy_ij = mark(arr_copy_ij, i + 1, j + 1, v)
                    arr_copy_ij = AutomaticSimpleProcessing(arr_copy_ij, value_list_copy_ij)
                    if detection_error(arr_copy_ij):
                        #  判断时候可以结束
                        if detection(arr_copy_ij):
                            return arr_copy_ij
                        else:
                            # 说明V 有概念是对的 但是 还需要继续尝试
                            return_jiashe_data = assume(arr_copy_ij, value_list_copy_ij)
                            if return_jiashe_data is None:
                                # 说明 当前 V 不合适 后续的测试导致 错误 继续下一个V 的尝试
                                pass
                            else:
                                return return_jiashe_data
                    else:
                        pass
                        # 说明  v 不合适  无须处理 使用copy 的原始数据继续尝试
                #  到这里说明 某一格子 所有可能都不合适， 上一轮的尝试 是有问题的
                return None


def handle(value_list):
    arr = init()
    # 计算坐标 并填充 默认值，以及默认值所在行列矩阵 没有重复
    for value in value_list:
        x = int((value // 100) % 10)
        y = int((value // 10) % 10)
        v = int(value % 10)
        arr = mark(arr, x, y, v)

        # 先过一边自动处理
    arr = AutomaticSimpleProcessing(arr, value_list)
    printArr(arr)
    if not detection(arr):
        print("使用假设法，尝试填充")
        arr = assume(arr, value_list)
    print("数独填充完毕")
    printArr(arr)
    result = np.zeros((9, 9), dtype=int)
    for i in range(9):
        for j in range(9):
            result[i][j] = ivn_ok(arr[i][j])
    return result

if __name__ == "__main__":
    # 初始条件 xyv
    # X 行 从1开始 对应网上 教程的A
    # Y 列 从1开始 对应网上 教程的1
    # V 值  该点的数据
    value_list = {159, 186,
                  232, 267, 285,
                  314, 323, 381,
                  431, 466, 488,
                  524, 558,
                  616, 638, 641,
                  711, 753, 792,
                  822,
                  944, 957, 999
   }
    result = handle(value_list)
    # print(f"{result}")

